"""
难度：中等
给你两个字符串 s1 和 s2 ，
写一个函数来判断 s2 是否包含 s1 的排列。
如果是，返回 true ；否则，返回 false 。
换句话说，s1 的排列之一是 s2 的 子串 。
示例 1：
输入：s1 = "ab" s2 = "eidbaooo"
输出：true
解释：s2 包含 s1 的排列之一 ("ba").
示例 2：
输入：s1= "ab" s2 = "eidboaoo"
输出：false
"""

import collections

class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        left, right =0, 0

        s1_count = collections.Counter(s1)

        window_count = collections.Counter()

        window_size = len(s1)

        while right < len(s2):
            window_count[s2[right]] += 1
            if right - left + 1 >= window_size:
                if window_count == s1_count:
                    return True
                window_count[s2[left]] -= 1

                if window_count[s2[left]] == 0:
                    del window_count[s2[left]]
                left += 1
            right += 1
            
        return False

    
# 方法一：滑动窗口
    # def checkInclusion(self, s1: str, s2: str) -> bool:
    #     n, m = len(s1), len(s2)
    #     if n > m:
    #         return False
    #     cnt1 = []
    #     cnt2 = []
    #     for i in range(n):
    #         s1[i] - 'a'
#方法二：    单指针方式


# 方法三： 双指针方式


